package com.qch.leecode.cyc2018.algorithm.a3_greedy;

import com.qch.leecode.cyc2018.util_comom.Common;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 算法思想：贪心算法：435. Non-overlapping Intervals 不重叠的区间个数(Medium)
 * 贪心算法：保证每次操作都是局部最优的，并且最后得到的结果是全局最优的。
 * https://leetcode.cn/problems/non-overlapping-intervals
 * @Author qch
 * @Date 2022/11/17
 * 自己解题：
 * 又是一个没看懂题目的题（哦，数学的区间）
 * 解题没有思路
 * 参考：先按照结束区间排序：[L,R]按照R从小到大排序【非常重要对于移除最小区间】(如果需要移除最多区间，则倒序（还需要思考，不确定）)
 *         greedy[L,R][R_,Min]
 *
 * 题目：给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。
 * 返回 需要移除区间的最小数量，使剩余区间互不重叠 。
 *
 *
 * 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
 * 输出: 1
 * 解释: 移除 [1,3] 后，剩下的区间没有重叠。
 *
 * 输入: intervals = [ [1,2], [1,2], [1,2] ]
 * 输出: 2
 * 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
 *
 */
public class L2_NonOverlappingIntervals435 {
    public static void main(String[] args) {
        int[][] intervals={{1,2},{2,3},{3,4},{1,3}};
       // int[][] intervals={{1,2}, {1,2}, {1,2}};
       int count = own_eraseOverlapIntervals(intervals);
       System.out.println(count);
//        Arrays.sort(intervals, new Comparator<int[]>() {
//            @Override
//            public int compare(int[] o1, int[] o2) {
//                return o1[1]<o2[1]?-1:o1[1]==o2[1]?0:1;
//            }
//        });
//        Common.toString(intervals);
    }


    /**
     * [L,R]按照R从小到大排序(如果需要移除最多区间，则倒序（还需要思考，不确定）)
     * greedy[L,R][R_,Min]
     * @param intervals
     * @return
     */
    public static int own_eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] < o2[1] ? -1 : o1[1] == o2[1] ? 0 : 1;
            }
        });
        Common.toString(intervals);
        int remove = 0;
        int right = intervals[0][1];
        int left;
        for (int i = 1; i < intervals.length; i++) {
            left = intervals[i][0];
            //左区间小于前者右区间的重叠，需要删除
            if (left < right) {
                remove++;
            } else {
                right = intervals[i][1];
            }
        }
        return remove;
    }
}
